package test;

//二叉树剪枝： https://leetcode.cn/problems/binary-tree-pruning/
//时间复杂度： O(n)
public class PruneTree {
	
	//dfs: 返回所有不包含1的子树的原二叉树
    public TreeNode dfs(TreeNode root){
        if(root==null) return null;
        
        TreeNode l=dfs(root.left); 
        TreeNode r=dfs(root.right);
        //如果root成为叶子节点，则返回null
        if(l==null&&r==null&&root.val==0){
            return null;
        }
        root.left=l;
        root.right=r;
        return root;
    }
    public TreeNode pruneTree(TreeNode root) {
        return dfs(root);
    }
}
